The present invention relates generally to techniques for configuring optical networks and other types of communication networks, and more particularly to network configuration techniques which permit fast restoration of signal paths after a failure in a link or node of the network.
Ring networks, such as networks based on synchronous optical network (SONET) rings, are becoming increasingly popular due to their fast restoration capability in the presence of node or link failures. A ring network may be viewed as any network which includes a set of interconnected rings of nodes. For a given network including a set of rings and a set of node-to-node traffic demands, the routing aspect of ring network design generally involves routing each demand across the ring network from its source node to its destination node such that the overall network cost, as a function of the ring capacities required by the routing, is minimized.
There are two types of ring interconnections that are used in ring networks: Single Ring Interworking (SRI) and Dual Ring Interworking (DRI). SRI is a simple interworking technique which uses only one hub node serving as a gateway to move traffic from one ring to another. The hub node has to be a common node shared by the two rings. SRI for a given demand is uniquely defined by two rings and a hub node for that demand. There may be multiple common nodes between two rings, and any one of the common nodes can be used in SRI. Although SRI has the advantage of simplicity, it provides no protection against hub node failure.
DRI is designed to overcome this reliability weakness at the price of higher complexity. In DRI, two hub nodes are selected from each ring and paired with the hub nodes on another ring. Cross-ring traffic is moved by sending two copies from one ring to the other via two hub pairs, with one copy sent on each hub pair. DRI is described in greater detail in, for example, B. Doshi et al, xe2x80x9cDual Ring Interworking: High Penalty Cases and How to Avoid Them,xe2x80x9d Proceedings of ITC 15, June, 1997. Examples of ring-based architectures which utilize DRI include bidirectional line-switched rings (BLSRI and path switched rings.
Although ring-based architectures based on DRI can provide very fast restoration, e.g., on the order of milliseconds, the increased restoration speed is achieved at the expense of added cost and increased operational complexity. Both the added cost and the increase in operational complexity can be traced to the above-described DRI feature. It is therefore apparent that a need exists for an improved network architecture which can provide the fast restoration capability commonly associated with DRI, but with a substantially reduced cost and complexity.
The invention provides techniques for routing capacity demands in a ring-based network while avoiding the cost and complexity typically associated with DRI. In an illustrative embodiment, a network includes at least one ring having a pair of hub nodes and a number of additional nodes. A pair of minimum-weight routing trees is generated for the ring, with each of the routing trees specifying paths between nodes of the ring, and having as its root a corresponding one of the hub nodes of the ring. The routing trees are utilized to route capacity demands from nodes of the ring to other portions of the network, such as other rings. The routing trees for a given ring of the network are configured such that the two hub nodes of the ring are adjacent in each of the routing trees of that ring. In addition, the routing trees for the given ring are directed edge disjoint, such that if a link corresponding to one edge of a tree fails, an affected demand is routed to the other hub node of the ring using the other routing tree of the ring. A capacity demand originating at one of the additional nodes of the ring is therefore routed through a first routing tree of the ring to a first hub node of the ring, while a restoration path for the given demand is provided through a second routing tree of the ring to a second hub node of the ring.
In accordance with another aspect of the invention, a network may be configured to include pairs of xe2x80x9csuperxe2x80x9d hub nodes, with pairs of the hub nodes for rings in the network each being assigned to pairs of the super hub nodes. A pair of routing trees generated for a given pair of the super hub nodes is then utilized to route demands for capacity from one of the hub nodes to the super hub nodes. The routing trees for a given pair of super hub nodes have characteristics similar to those identified above for routing trees of ring hub nodes.
A dual hubbed tree network architecture in accordance with the invention not only provides the advantage of predefined failure-independent restoration paths, but also allows more efficient capacity sharing while eliminating the added cost and complexity associated with conventional DRI. These and other features and advantages of the present invention will become more apparent from the accompanying drawings and the following detailed description.